/**
 * @Author Fizz Pu
 * @Date 2020/9/11 下午8:43
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

import java.util.ArrayList;
import java.util.List;
import java.util.StringJoiner;

/**
 * 给定一个二叉树，返回所有从根节点到叶子节点的路径。
 *
 * 说明: 叶子节点是指没有子节点的节点。
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Lee257 {
    // 典型的dfs的题目
    // 对于树的话可以用栈，也可以用递归
    // 用用递归简单地写
    private List<String> res = new ArrayList<>();
    private List<CharSequence> ch = new ArrayList<>();

    public List<String> binaryTreePaths(TreeNode root){
            dfs(root);
            return res;
    }

    void dfs(TreeNode root){
        if(root == null)return;
        ch.add(String.valueOf(root.val)); // 此节点不为空，那么加到结果集

        if (root.right == null && root.left == null){ // 叶子节点，生成结果
            res.add(joinStr(ch));
        }
        else {
            if(root.left != null){
                binaryTreePaths(root.left);
                ch.remove(ch.size()-1); // 回溯
            }
            if(root.right != null){
                binaryTreePaths(root.right);
                ch.remove(ch.size()-1); // 回溯
            }
        }
    }

    // 查下CharSequence是个啥
    private  String joinStr(List<CharSequence> ch){
        CharSequence[] strs = ch.toArray(new CharSequence[0]);
        return String.join("->", strs);
    }

    // 失败代码
    // 这个题不就是排列树问题吗
    /*public List<String> binaryTreePaths(TreeNode root) {
        if(root == null)return res;

        ch.add(String.valueOf(root.val));
        // 遇到叶子节点
        if(root != null && root.right == null && root.left == null){
            res.add(joinStr(ch));
            // 回退
            ch.remove(ch.size()-1);
            return null; // 返回上层
        }
        if(root.left != null)binaryTreePaths(root.left);
        if(root.right != null)binaryTreePaths(root.right);
        return res;
    }
    */


}

